home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / DiskUtil / Crunch / XPK / DOCS / HUFF.DOC < prev    next >
Text File  |  1992-08-10  |  10KB  |  218 lines
  1.  
  2.  
  3.                                     HUFF
  4.                    A dynamic huffman cruncher/decruncher
  5.                                 Version 0.62
  6.                        Copyright 1992 by M.Zimmermann
  7.  
  8.  
  9.  
  10.                              License/Disclaimer
  11.                              ------------------
  12.  
  13.    This  library may be freely distributed with the XPK compression package,
  14. as  long  as  it is kept in its original, complete, and unmodified form.  It
  15. may  not  be  distributed  by  itself or in a commercial package of any kind
  16. without my permission.
  17.  
  18.    This  program  is  distributed  in  the  hope that it will be useful, but
  19. WITHOUT  ANY  WARRANTY; without even the implied warranty of MERCHANTABILITY
  20. or FITNESS FOR A PARTICULAR PURPOSE.
  21.  
  22.  
  23.  
  24.                                About Huffmans
  25.                                --------------
  26.  
  27. The  idea  of  a  huffman  crunch is as follows:  often used bytes (ie 8 bit
  28. codes) get a shorter code than 8 bits, fi 5 bits.  So everytime one of these
  29. bytes  occurs in the source file I save (in this example) 3 bits in the dest
  30. file.  To find out the optimum codes for each byte there is a simple method:
  31. A  tree  is  to  be  constructed so that the path from the root to each leaf
  32. reflects  the  optimum (ie huffman) code.  Unfortunately most computers (the
  33. Amiga,  too)  are  byte-oriented,  which  means a rather complex handling of
  34. codes  that  are  not  a  multiple  of  8 bits.  This results in pretty slow
  35. compression  &  decompression.   So  this  means  that  the  xpkHUFF.library
  36. probably  won't be used for normal circumstances, but, as Dominik stated, it
  37. may serve well as an example library.
  38.  
  39. There are three different huffman crunch algorithms known:
  40.  
  41. · static   compression/decompression
  42. · dynamic  compression/decompression
  43. · adaptive compression/decompression
  44.  
  45.  
  46. What are the differences?
  47.  
  48. The  static  huffman  uses a fix table to represent each byte of the source.
  49. This,  of  course,  makes  sense  only,  if  the structure of the data to be
  50. crunched  is known.  In this case (for instance crunching an english text) a
  51. fix  table of codes is embedded in the code.  Crunching other data than what
  52. the  table  was  generated  for will probably result in worse compression or
  53. even expansion.
  54.  
  55.    This  is  what  a  dynamic  huffman  is  avoiding:   it  first  creates a
  56. statistics  table  reflecting  the  frequency  every  byte  occurs  with and
  57. generates  a special tree/table for this case, so the dynamic huffman does a
  58. good compression for this special data.
  59.  
  60.    But there is something that can be improved, anyway:  imagine, there is a
  61. data  block which contains many 'a's in it's first part and many 'z's in the
  62. last  part....   The  dynamic huffman would represent the 'a's and 'z's with
  63. short  codes,  of  course.   But  it  probably  would  be even better if the
  64. crunch/decrunch  tree  would  reflect  the  *current*  data beeing processed
  65. instead of the whole block, thus in resulting shorter codes for 'a' and 'z',
  66. depending  of  the  position  in  the  data block.  This is what an adaptive
  67. huffman  deals with:  it creates the tree while crunching, without doing any
  68. statistics  or  tree creation before crunching.  It permanently updates it's
  69. internal huffman tree.  Therefore it doesn't have to include the information
  70. about the decrunch tree in the crunched data.
  71.  
  72.  
  73.  
  74.                        Final words about huffmans ...
  75.                        ------------------------------
  76.  
  77.    A  stand-alone huffman will never achieve crunch results as fine as those
  78. reached with most other crunchers, for these will not only regard the number
  79. of  occurances  for  each  byte (as huffman does), but sequels of byte, too.
  80. This  means:   If  you  create  all permutations of a datablock, the huffman
  81. crunched  will  always  have  the  same  length.   Others won't, as they are
  82. depending on the order of the crunched data, too.
  83.  
  84.  
  85.  
  86.                                 Description
  87.                                 -----------
  88.  
  89.    The   library  'xpkHUFF.library'  implements  a  dynamic  huffman  crunch
  90. algorithm,  even  though the adaptive might result in slightly better crunch
  91. results.  However, this is more complex to implement and I'm using a maximum
  92. buffer  size  of  64K,  so this is a little bit like an adaptive huffman for
  93. large files.
  94.  
  95.    If I should have lots of spare time I will probably implement an adaptive
  96. huffman crunch algorithm.  This new library will be called xpkHUFF, too, and
  97. new  xpkHUFF.libraries  will  always  handle  output  generated  by  earlier
  98. versions.
  99.  
  100.    The  xpkHUFF.library  supports  a totally unsafe (but a little bit better
  101. than  simple  eor  :-)  encryption.  Please note that crunch/decrunch speeds
  102. decrease when encryption is used.
  103.  
  104.  
  105.  
  106.                                The source ...
  107.                                --------------
  108.  
  109.   The  source  is  provided,  so you might have a look at different decrunch
  110. codes.   Please  note:  The only code I tested intensively is the byte/cache
  111. decrunch  code,  which  was  used  to  create  the  library included in this
  112. package.   For  it's the fasted code, you probably won't want to use another
  113. one.  However, this might help you to understand what huffmans are about.
  114.  
  115.    If you have never written a huffman, have a look at it, a huffman code is
  116. a  pretty good idea.  If you *have* written a huffman code and it's *faster*
  117. than mine, please let me know, I will then update xpkHUFF.library.
  118.  
  119.  
  120.  
  121.                                Implementation
  122.                                --------------
  123.  
  124.    If  you  should  see an errormessage saying output buffer too small while
  125. crunching  *and*  encrypting,  this  means you tried to crunch and encrypt a
  126. file  that  would  crunched  and encrypted be larger than the original file.
  127. This should occur only with very small files (for I have a minimum file size
  128. due  to  tables) or with files that have been crunched already and therefore
  129. would expand during crunch.
  130.  
  131.    A technical note:  this could also happen, if the last chunk of a file to
  132. be crunched/encrypted would be dimensioned too small by xpkmaster.library.
  133.  
  134.    However,  in this case you cannot encrypt the fcnt = in_idx - anchor) > 2)
  135.     {
  136.       if (cnt <= 18)    /* short rle */
  137.         {
  138.           ++cnt_srle;
  139.           *out_idx++ = cnt - 3;
  140.           *out_idx++ = c;
  141.         }
  142.       else
  143.         /* long rle */
  144.         {
  145.           ++cnt_lrle;
  146.           cnt -= 19;
  147.           *out_idx++ = 16 + (cnt & 0x0F);
  148.           *out_idx++ = cnt >> 4;
  149.           *out_idx++ = c;
  150.         }
  151.  
  152.       ctrl_bits = (ctrl_bits << 1) | 1;
  153.       continue;
  154.     }
  155.  
  156.       /* look for pattern if 2 or more characters remain in the input buffer */
  157.  
  158.       in_idx = anchor;
  159.  
  160.       if ((inbuff_end - in_idx) > 2)
  161.     {
  162.       /* locate the offste of possible pattern i sliding dictionary */
  163.  
  164.       ++cnt_hashes;
  165.       hash = ((((in_idx[0] & 15) << 8) | in_idx[1]) ^ ((in_idx[0] >> 4) | (in_idx[2] << 4))) & hash_len;
  166.  
  167.       pat_idx = hash_tbl[hash];
  168.       hash_tbl[hash] = in_idx;
  169.  
  170.       /* compare characters if we're within 4098 bytes */
  171.  
  172.       if ((gap = in_idx - pat_idx) <= 4098)
  173.         {
  174.           while (in_idx < inbuff_end && pat_idx < anchor && *pat_idx == *in_idx && (in_idx - anchor) < 271)
  175.         {
  176.           in_idx++;
  177.           pat_idx++;
  178.         }
  179.  
  180.           /* store pattern if it's more than 2 characters */
  181.  
  182.           if ((cnt = in_idx - anchor) > 2)
  183.         {
  184.           gap -= 3;
  185.  
  186.           if (cnt <= 15)/* short pattern */
  187.             {
  188.               ++cnt_spat;
  189.               *out_idx++ = (cnt << 4) + (gap & 0x0F);
  190.               *out_idx++ = gap >> 4;
  191.             }
  192.           else
  193.             {
  194.               ++cnt_lpat;
  195.               *out_idx++ = 32 + (gap & 0x0F);
  196.               *out_idx++ = gap >> 4;
  197.               *out_idx++ = cnt - 16;
  198.             }
  199.  
  200.           ctrl_bits = (ctrl_bits << 1) | 1;
  201.           continue;
  202.         }
  203.         }
  204.     }
  205.  
  206.       /* can't compress this character so copy it to outbuff */
  207.  
  208.       ++cnt_nocompr;
  209.       *out_idx++ = c;
  210.       in_idx = ++anchor;
  211.       ctrl_bits <<= 1;
  212.     }
  213.   /* save last load of control bits */
  214.  
  215.   ctrl_bits <<= (16 - ctrl_cnt);
  216.   *ctrl_idx = ctrl_bits;
  217.  
  218.   /* and return size of compressed buf